package problem.year2021.march;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
 * 返回 s 所有可能的分割方案。
 * 示例:
 * 输入: "aab"
 * 输出:
 * [
 * ["aa","b"],
 * ["a","a","b"]
 * ]
 * 通过次数73,128
 * 提交次数102,296
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/palindrome-partitioning
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class March7 {
    // 深度搜索+动态规划+回溯算法
    public List<List<String>> partition(String s) {
        /**
         * 对于一个字符串而言，要是是回文串，翻转后的字符串等于当前字符串就是回文字符串
         * 最基础的分割方案是将单字母分割一遍，然后组合单字母，发现有可以分割项，提出来，在分割一遍就OK了
         */
        char[] chars = s.toCharArray();
        int len = chars.length;
        List<List<String>> answer = new LinkedList<>();
        List<String> temp = new ArrayList<>();
        for (char c : chars) {
            temp.add("" + c);
        }
        answer.add(temp);
        for (int i = 2; i <= len; ++i) {

        }

        return null;
    }
    class Solution {
        boolean[][] f;
        List<List<String>> ret = new ArrayList<List<String>>();
        List<String> ans = new ArrayList<String>();
        int n;

        public List<List<String>> partition(String s) {
            n = s.length();
            f = new boolean[n][n];
            for (int i = 0; i < n; ++i) {
                Arrays.fill(f[i], true);
            }

            for (int i = n - 1; i >= 0; --i) {
                for (int j = i + 1; j < n; ++j) {
                    f[i][j] = (s.charAt(i) == s.charAt(j)) && f[i + 1][j - 1];
                }
            }

            dfs(s, 0);
            return ret;
        }

        public void dfs(String s, int i) {
            if (i == n) {
                ret.add(new ArrayList<String>(ans));
                return;
            }
            for (int j = i; j < n; ++j) {
                if (f[i][j]) {
                    ans.add(s.substring(i, j + 1));
                    dfs(s, j + 1);
                    ans.remove(ans.size() - 1);
                }
            }
        }
    }
    class Solution2 {
        int[][] f;
        List<List<String>> ret = new ArrayList<List<String>>();
        List<String> ans = new ArrayList<String>();
        int n;

        public List<List<String>> partition(String s) {
            n = s.length();
            f = new int[n][n];

            dfs(s, 0);
            return ret;
        }

        public void dfs(String s, int i) {
            if (i == n) {
                ret.add(new ArrayList<String>(ans));
                return;
            }
            for (int j = i; j < n; ++j) {
                if (isPalindrome(s, i, j) == 1) {
                    ans.add(s.substring(i, j + 1));
                    dfs(s, j + 1);
                    ans.remove(ans.size() - 1);
                }
            }
        }

        // 记忆化搜索中，f[i][j] = 0 表示未搜索，1 表示是回文串，-1 表示不是回文串
        public int isPalindrome(String s, int i, int j) {
            if (f[i][j] != 0) {
                return f[i][j];
            }
            if (i >= j) {
                f[i][j] = 1;
            } else if (s.charAt(i) == s.charAt(j)) {
                f[i][j] = isPalindrome(s, i + 1, j - 1);
            } else {
                f[i][j] = -1;
            }
            return f[i][j];
        }
    }
}
